package com.codebuffer.leetcode;

import java.util.Deque;
import java.util.concurrent.LinkedBlockingDeque;

public class ReorderList {

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void reorderList(ListNode head) {
        Deque<ListNode> deque = new LinkedBlockingDeque<ListNode>();
        ListNode next = head.next;
        while (null!=next){
            deque.push(next);
            next = next.next;
        }
        int i = 0;
        ListNode node = head;
        while (!deque.isEmpty()){
            if(i%2==0){
                next = deque.pollFirst();
            }else {
                next = deque.pollLast();
            }
            next.next = null;
            node.next = next;
            i++;
            node = node.next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode4 = new ListNode(4);
        ListNode listNode3 = new ListNode(3,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);
        reorderList(listNode1);
    }
}
